package com.chunlin.list.LinkList;

//不同点ArrayList                                      LinkedList
//存储空间上物理上一定                        连续逻辑上连续，但物理上不一定连续
//随机访问支持O(1)                                    不支持：O(N)
//头插需要搬移元素，效率低O(N)               只需修改引用的指向，时间复杂度为O(1)
//插入空间不够时需要扩容                               没有容量的概念
//应用场景元素高效存储+频繁访问                   任意位置插入和删除频繁

//【说明】
//1. LinkedList实现了List接口
//2. LinkedList的底层使用了双向链表
//3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
//4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
//5. LinkedList比较适合任意位置插入的场景


import java.util.*;

public class LinkListTest {
    public static void test1() {
        // 构造一个空的LinkedList
        List<Integer> list1 = new LinkedList<>();

        // 使用ArrayList构造LinkedList,但是字符串共享,如果要不共享,需要遍历ArrayList,然后单独new字符串
        List<String> list2 = new ArrayList<>();
        list2.add("JavaSE");
        list2.add("JavaWeb");
        list2.add("JavaEE");
        List<String> list3 = new LinkedList<>(list2);
        System.out.println(list3);
    }

    //LinkedList的其他常用方法
    public static void test2() {
        //boolean add(E e)
        // 尾插 e
        //如果这样使用List来进行接收,那么意味着只能使用List当中实现的接口
        // 因为LinkedList也实现了Deque的接口,所以如果想要使用Deque的接口,需要使用LinkedList来进行接收
//        List<Integer> list = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        //void addFirst(E e)
        //头插
        list.addFirst(6);
        //addLast(E e)
        //尾插
        list.addLast(7);

        System.out.println(list);

        //void add(int index, E element) 将 e 插入到 index 位置
        //在下标为1的位置插入0
        list.add(1, 8);
        System.out.println(list);

        //boolean addAll(int index, Collection<? extends E> c) 在下标index尾插 c 中的元素
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        list.addAll(2, arrayList);
        System.out.println(list);

        // remove(): 删除第一个元素，内部调用的是removeFirst()
        list.remove();
        System.out.println(list);

        //删除第一个元素
        list.removeFirst();
        System.out.println(list);

        //删除最后一个元素
        list.removeLast();
        System.out.println(list);

        //E remove(int index) 删除 index 位置元素
        list.remove(2);
        System.out.println(list);

        //boolean remove(Object o) 删除遇到的第一个 o
        list.remove((Integer) 2);
        System.out.println(list);

        // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
        if (!list.contains(6)) {
            list.add(6);
            System.out.println(list);
        }

        // indexOf(elem): 从前往后找到第一个elem的位置
        System.out.println(list.indexOf((Integer) 1));
        // lastIndexOf(elem): 从后往前找第一个1的位置
        System.out.println(list.lastIndexOf((Integer) 1));

        // get(index): 获取指定位置元素
        int elem = list.get(0);
        System.out.println(elem);
        // set(index, elem): 将index位置的元素设置为elem
        list.set(0, 100);
        System.out.println(list);

        // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
        List<Integer> copy = list.subList(1, 7);
        System.out.println(copy);

        //得到单链表的长度
        System.out.println(copy.size());

        //void clear() 清空
        copy.clear();
        System.out.println(copy.size());

    }

    //LinkList的遍历
    public static void test3() {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); // add(elem): 表示尾插
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        System.out.println(list.size());
        // foreach遍历
        for (int e : list) {
            System.out.print(e + " ");
        }
        System.out.println();
        System.out.println();

        //使用迭代器遍历---正向遍历
        ListIterator<Integer> iterator = list.listIterator();
        //迭代器的下标认为是在线性表的-1位置
        while(iterator.hasNext()) {
            System.out.println(iterator.next() + " ");
        }
        System.out.println();

        // 使用反向迭代器---反向遍历
        ListIterator<Integer> iterator1 = list.listIterator(list.size());
        while (iterator1.hasPrevious()) {
            System.out.println(iterator1.previous() + " ");
        }

    }

    public static void test4() {
    }

    public static void test5() {
    }

    public static void test6() {
    }

    public static void test7() {
    }


    public static void main(String[] args) {
//        test1();
//        test2();
        test3();
    }
}
